package com.taldh.algorithm.sort;

/**
 * date 2020/6/3
 *
 * @author 袁小黑
 * @version 1.0.0
 **/

public class QuickSort {


    public <T> void sort(Comparable<T>[] data) {
        int low=0,high=data.length-1;
        quickSort(data, low, high) ;
    }

    private <T> int partition(Comparable<T>[] data, int low, int high)
    {
        Comparable<T> temp,pivotkey;
        pivotkey=data[low]; //选取支点
        temp=pivotkey;  //暂存支点
        while (low<high)  //条件，相等则结束
        {
            while (low<high && data[high].compareTo((T) pivotkey)>=0)
            {
                high--;//左移
            }
            data[low]=data[high];//覆盖
            while (low<high && data[low].compareTo((T) pivotkey)<=0)
            {
                low++;  //右移
            }
            data[high]=data[low];//覆盖
        }
        data[low]=temp; //恢复
        return low;  //返回分界点位置
    }

    private <T> void quickSort(Comparable<T>[] data, int low, int high)
    {
        int pivot;
        if (low<high)
        {
            pivot= partition(data,low,high); //获得分界点位置
            quickSort(data,low,pivot-1); //排左边
            quickSort(data,pivot+1,high);//右边
        }
    }


}
